#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define Data_type int
typedef struct Node
{
    Data_type data;
    struct Node *left;
    struct Node *right;

} treeNode, *BinaryTree;

// 创建二叉树
BinaryTree createTree()
{

    Data_type c;
    scanf("%d", &c);
    if (c == '*')
    {
        return NULL;
    }
    BinaryTree root = (BinaryTree)malloc(sizeof(treeNode));
    if (root == NULL)
    {
        printf("内存分配失败\n");
    }
    root->data = c;
    root->left = createTree(); // 递归创建左孩子

    root->right = createTree(); // 递归创建右孩子
    return root;
}
// 先序遍历：根左右
void preorder_Traversal(BinaryTree root)
{
    if (root == NULL) // 如果是一个空树则返回
    {
        return;
    }
    // 访问根
    printf("%c\t", root->data);
    // 访问左孩子
    preorder_Traversal(root->left); // 如果左孩子不存在则返回上一层 父节点
    // 访问右孩子
    preorder_Traversal(root->right);
}
// 销毁二叉树
void destory_BinaryTree(BinaryTree root)
{
    if (root == NULL)
    {
        return;
    }
    // 释放左子树
    destory_BinaryTree(root->left);
    // 释放右子树
    destory_BinaryTree(root->right);
    // 释放根节点
    free(root);
    root = NULL;
}
void main()
{
    BinaryTree root = createTree();
    preorder_Traversal(root);
    destory_BinaryTree(root);
}